"""
题目：找到单链表中倒数第 k 个节点（k 为正整数），若不存在则返回 None。
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


"""
找到倒数第k个节点，并返回对应的node对象(不是整个链表的首节点!)
"""
def find_kth_from_end(head, k):
    # 处理空链表或k无效的情况
    # k为正整数
    if not head or k <= 0:
        return None
    # 初始化两个指针，都指向头节点
    first = head
    second = head
    # 先让first指针向前移动k步
    for _ in range(k):
        if not first:  # 如果k超过链表长度，返回None
            return None
        first = first.next  # 移动first指针

    # 同时移动两个指针，直到first到达末尾;
    # 本质就是:让first和second两个指针差k个位置，然后first、second继续后移，直到first移动到链表尾部的后面一位，这时候，从后往前看，second就是倒数第K个节点位置
    while first:
        first = first.next
        second = second.next
    # 此时second指向倒数第k个节点
    return second


def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


def get_node_value(node):
    return node.val if node else None  # 返回节点值，处理空节点


# 测试
head = create_linked_list([1, 2, 3, 4, 5])
print(get_node_value(find_kth_from_end(head, 2)))  # 输出: 4（倒数第2个节点）
print(get_node_value(find_kth_from_end(head, 6)))  # 输出: None（k超过长度）
